package Class022;

import Class004.BasicSorts;
import Utils.ArrayUtils;

import java.util.Arrays;

public class MergeQuestions {
    public static void main(String[] args) {
        test();
    }

    public static int bruteForce(int[] arr) {
        int smallSum = 0;
        for(int end = 1; end < arr.length; end++) {
            for(int i = 0; i < end; i++) {
                if(arr[i] <= arr[end]) {
                    smallSum += arr[i];
                }
            }
        }
        return smallSum;
    }

    public static int mergeAndCalSmallSum(int[] arr, int l, int r, int m) {
        int[] help  = new int[r - l + 1];
        int smallSum = 0;
        int lp = l, rp = m + 1, index = 0;
        while(lp <= m && rp <= r) {
            if(arr[lp] <= arr[rp]) {
                help[index++] = arr[lp];
                smallSum += arr[lp++] * (r - rp + 1);
            }else {
                help[index++] = arr[rp++];
            }
        }
        while(lp <= m) {
            help[index++] = arr[lp++];
        }
        while(rp <= r) {
            help[index++] = arr[rp++];
        }
        for(int i = 0; i < help.length; i++) {
            arr[i + l] = help[i];
        }
        return smallSum;
    }

    public static int mergeWithSmallSum(int[] arr, int l, int r) {
        if(l == r) return 0;
        int m = l + ((r - l) >> 1);
        int left = mergeWithSmallSum(arr, l, m);
        int right = mergeWithSmallSum(arr, m + 1, r);
        return left + right + mergeAndCalSmallSum(arr, l, r, m);
    }

    public static int mergeWithSmallSumIter(int[] arr) {
        int group = 1;
        int N = arr.length;
        int res = 0;
        while (group < N) {
            for(int l = 0, m, r; l < N; l += (group << 1)) {
                if(l + group >= N) break;
                m = l + group - 1;
                r = Math.min(l + (group << 1) - 1, N - 1);
                res += mergeAndCalSmallSum(arr, l, r, m);
            }
            if(group >= (N >> 1)) break;
            group <<= 1;
        }
        return res;
    }

    //求数组的小和
    //小和：一个数所有左边比他小的数的和
    //[1,3,5,4,2,6]的小和为27
    public static int getSmallSum(int[] arr, boolean rec) {
        if(rec) return mergeWithSmallSum(arr, 0, arr.length - 1);
        return mergeWithSmallSumIter(arr);
    }

    public static void test() {
        int time = 10;
        int amount = 20000, max = 1000;
        int errTime = 0;
        System.out.println("Correctness Test:");
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
//            int[] base = {1,3,5,2,4,6};
            int bru = bruteForce(base);
            int mer = getSmallSum(base, false);
            if (bru != mer) {
                System.out.println(Arrays.toString(base));
                System.out.println("Should be:" + bru);
                System.out.println("Wrong answer:" + mer);
                errTime++;
            }
        }
        if (errTime == 0) {
            System.out.println("All clear.");
        } else {
            System.out.println("Errors:" + errTime + "/" + time);
            System.out.println("Accuracy:" + (time - errTime) * 1.0 / time);
            return;
        }

        System.out.println("Time test:");
        long s, e;
        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            bruteForce(base);
        }
        e = System.currentTimeMillis();
        System.out.println("Brute:" + (e - s) + "ms");

        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            getSmallSum(base, true);
        }
        e = System.currentTimeMillis();
        System.out.println("Merge(Rec):" + (e - s) + "ms");

        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            getSmallSum(base, false);
        }
        e = System.currentTimeMillis();
        System.out.println("Merge(Ite):" + (e - s) + "ms");
    }
}
